#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 22:28
# @USER    : Shengji He
# @File    : CombinationSum2.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        Given a collection of candidate numbers (candidates) and a target number (target), find all unique
        combinations in candidates where the candidate numbers sums to target.

        Each number in candidates may only be used once in the combination.

        Note:
            - All numbers (including target) will be positive integers.

            - The solution set must not contain duplicate combinations.

        Example 1:
            Input: candidates = [10,1,2,7,6,1,5], target = 8,

            A solution set is:

            [
              [1, 7],

              [1, 2, 5],

              [2, 6],

              [1, 1, 6]

            ]

        Example 2:
            Input: candidates = [2,5,2,1,2], target = 5,

            A solution set is:

            [

              [1,2,2],

              [5]

            ]

        :param candidates: List[int]
        :param target: int
        :return: List[List[int]]
        """
        candidates.sort()
        ls = 0
        ans = []
        while ls < len(candidates) and candidates[ls] <= target:
            div = target // candidates[ls]
            div = min([div, candidates.count(candidates[ls])])
            next_ls = ls + candidates.count(candidates[ls])
            while div > 0:
                temp = [candidates[ls]] * div
                res = target - div * candidates[ls]
                if res == 0:
                    ans.append(temp)
                elif res > candidates[ls]:
                    output = self.combinationSum2(candidates[next_ls:], res)
                    if not output:
                        pass
                    else:
                        for ele in output:
                            ans.append(temp + ele)
                else:
                    pass
                div -= 1
            ls = next_ls
        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [2,5,2,1,2]
    target = 5
    # nums = [10,1,2,7,6,1,5]
    # target = 8
    print(S.combinationSum2(nums, target))
    print('done')
